//
// Description: 6019. 替换数组中的非互质数
// Created by Loading on 2022/3/6.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> replaceNonCoprimes(vector<int> &nums) {
    int n = nums.size();
    vector<int> res;
    for (int i = 0; i < n; ++i) {
        int x = nums[i];
        // 当前值与结果数组中的值不断进行最大公约数判定
        while (!res.empty() && gcd(res.back(), x) > 1) {
            // 替换当前值为最小公倍数，继续判定
            x = lcm(res.back(), x);
            res.pop_back();
        }
        // 判定结束
        res.emplace_back(x);
    }

    return res;
}

int main() {
    vector<int> nums{287, 41, 49, 287, 899, 23, 23, 20677, 5, 825};
    auto res = replaceNonCoprimes(nums);
    for (auto x : res) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}